package base;

import java.util.HashMap;
import java.util.Map;

/**
 * @author mazouri
 * @create 2021-12-27 10:59
 */
public class _3_las {
    /**
     * 暴力
     */
    public int longestArithSeqLength1(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int diff = nums[j] - nums[i];
                int pre = j;
                int count = 2;
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[k] - nums[pre] == diff) {
                        count++;
                        pre = k;
                    }
                }
                res = Math.max(res, count);
            }
        }

        return res;
    }

    public static int longestArithSeqLength(int[] A) {
        if (A== null|| A.length < 2) {
            return 0;
        }
        // 两个数才能构成的等差,所以结果值初始化为 2
        int res = 2;
        // dp[diff][idx] 差值为 diff 的序列长度
        Map<Integer, Integer>[] dp = new HashMap[A.length];
        for (int i = 0; i < A.length; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                int diff = A[i] - A[j];
                // 如果 j 的前面也存在 diff 的等差序列，把它也加上
                if (dp[j].containsKey(diff)) {
                    dp[i].put(diff, dp[j].get(diff) + 1);
                } else {
                    dp[i].put(diff, 2);
                }
                res = Math.max(res, dp[i].get(diff));
            }
            for (Map<Integer, Integer> map : dp) {
                System.out.println(map);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        _3_las o = new _3_las();
        System.out.println(o.longestArithSeqLength(new int[]{20,1,15,3,10,5,8}));
    }
}
